{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Coin Change Problem\n",
    "\n",
    "##### Note: This problem has multiple solutions and is a classic problem in showing issues with basic recursion. If you are having trouble with this problem (or it seems to be taking a long time to run in some cases) check out the Solution Notebook and fully read the conclusion link for a detailed description of the various ways to solve this problem!\n",
    "\n",
    "\n",
    "This problem is common enough that is actually has its own [Wikipedia Entry](https://en.wikipedia.org/wiki/Change-making_problem)! \n",
    "\n",
    "____\n",
    "## Problem Statement\n",
    "Given a target amount **n** and a list (array) of distinct coin values, what's the fewest coins needed to make the change amount. \n",
    "\n",
    "For example:\n",
    "\n",
    "If n = 10 and coins = [1,5,10]. Then there are 4 possible ways to make change:\n",
    "\n",
    "* 1+1+1+1+1+1+1+1+1+1\n",
    "\n",
    "* 5 + 1+1+1+1+1\n",
    "\n",
    "* 5+5\n",
    "\n",
    "* 10\n",
    "\n",
    "With 1 coin being the minimum amount.\n",
    "\n",
    "    \n",
    "## Solution\n",
    "\n",
    "Implement your solution below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rec_coin(target,coins):\n",
    "    min_coins = target\n",
    "    \n",
    "    if target in coins:\n",
    "        return 1\n",
    "    else:\n",
    "        for value in [ c for c in coins if c<= target]:\n",
    "            num_coins = rec_coin(target-value, coins) + 1\n",
    "            min_coins = min(num_coins, min_coins)\n",
    "    return min_coins\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rec_coin(10,[1,5]) #2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rec_coin(63,[1,5,10,25])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Test Your Solution\n",
    "\n",
    "Run the cell below to test your function against some test cases. \n",
    "\n",
    "**Note that the TestCoins class only test functions with two parameter inputs, the list of coins and the target**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "RUN THIS CELL TO TEST YOUR FUNCTION.\n",
    "NOTE: NON-DYNAMIC FUNCTIONS WILL TAKE A LONG TIME TO TEST. IF YOU BELIEVE YOU HAVE A SOLUTION \n",
    "      GO CHECK THE SOLUTION NOTEBOOK INSTEAD OF RUNNING THIS!\n",
    "\"\"\"\n",
    "\n",
    "from nose.tools import assert_equal\n",
    "\n",
    "class TestCoins(object):\n",
    "    \n",
    "    def check(self,solution):\n",
    "        coins = [1,5,10,25]\n",
    "        assert_equal(solution(45,coins),3)\n",
    "        assert_equal(solution(23,coins),5)\n",
    "        assert_equal(solution(74,coins),8)\n",
    "        print ('Passed all tests.')\n",
    "# Run Test\n",
    "\n",
    "test = TestCoins()\n",
    "test.check(rec_coin)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## EXTRA\n",
    "\n",
    "Good luck and remember to read the solution notebook for this once you've think you have a solution!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
